﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 九宫格
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] array = new int[3,3];

            int[] arrTarget = new int[9];

            ArrayList copyList = new ArrayList();

            //生成产生九宫格的数据源
            for(int counst=0;counst<arrTarget.Length;counst++)
            {
                arrTarget[counst] = counst+1;
            }


            //for(int i=0;i<15;i++)
            //{
            //    for(int j=0;j<3;j++)
            //    {
            //        for(int k=0;k<3;k++)
            //        {
            //            for
            //        }
            //    }
            //}
            //for (int i = 0; i < arrTarget.Length; i++)
                //createNewD(array, arrTarget, i, copyList);

                createD(arrTarget, copyList);

            //int[,] a=new int[3,3]{{ 2, 9, 4 }, { 7, 5, 3 }, { 6, 1, 8 } };
            //bool flag=isPass(a);
            //print(a);
            Console.ReadLine();
            return;
        }

        static void createD(int[] targetArray,ArrayList resultSet)
        {
            for (int i=0;i<targetArray.Length;i++)
            {
                int[,] DArray = new int[3, 3];
                int[] target = (int[])targetArray.Clone();
                DArray[0, 0] = target[i];
                target[i] = -1;
                createD(DArray, target, resultSet,1);
            }
        }

        static void createD(int[,] DArray, int[] targetArray, ArrayList resultSet,int len)
        {
            if(len>=DArray.Length)
            {
                if(isPass(DArray))
                {
                    resultSet.Add(DArray);
                    print(DArray);
                }
                return;
            }
            int x = len % 3;
            int y = len / 3;
           // int i = 0;
            //int[] target = (int[])targetArray.Clone();
            //int[,] RDArray = (int[,])DArray.Clone();
            //while (i<9&&target[i]==-1)
            //{
            //    DArray[y, x] = target[i];
            //    target[i] = -1;
            //    createD(DArray, target, resultSet, len + 1);
            //    //i++;
            //}

            for(int i=0;i<targetArray.Length;i++)
            {
                if(targetArray[i]==-1)
                {
                    continue;
                }
                int[] target = (int[])targetArray.Clone();
                DArray[y, x] = target[i];
                target[i] = -1;
                createD(DArray, target, resultSet, len + 1);
            }
            //int[] target = (int[])targetArray.Clone();
            //DArray[y,x] = targetArray[i];
            //targetArray[i] = -1;
            //createD(DArray, target, resultSet, len + 1);
        }

        static bool isPass(int[,] arr)
        {
            int sum;

            //行
            for (int i = 0; i < arr.GetLength(0); i++)
            {
                sum = 0;
                for (int j = 0; j < arr.GetLength(1); j++)
                {
                    sum += arr[i, j];
                }
                if (sum != 15)
                {
                    return false;
                }
            }

            //列
            for (int i = 0; i < arr.GetLength(1); i++)
            {
                sum = 0;
                for (int j = 0; j < arr.GetLength(0); j++)
                {
                    sum += arr[j, i];
                }
                if (sum != 15)
                {
                    return false;
                }
            }

            //对角
            sum = arr[0, 0] + arr[1, 1] + arr[2, 2];
            if (sum != 15)
                return false;
            sum = arr[0, 2] + arr[1, 1] + arr[2, 0];
            if (sum != 15)
                return false;

            return true;
        }

        static void print(int[,] array)
        {
            for(int i=0;i<array.GetLength(0);i++)
            {
                Console.WriteLine("{0}\t{1}\t{2}",array[i,0], array[i, 1], array[i, 2]);
            }
            Console.WriteLine();
        }

        //static void createNewD(int[,] array,/*int line,int row,*/int[] arrTarget,int lowBegin/*,int[] arrLow*/,ArrayList copyList)
        //{

        //    //int lowNub = arrLow.Length;
        //    //for(int lowCounst=0;lowCounst<arrLow.Length;lowCounst++)
        //    //{
        //    //    if(arrLow[lowCounst]==-1)
        //    //    {
        //    //        lowNub = lowCounst;
        //    //        break;
        //    //    }
        //    //}
        //    if(lowBegin>=arrTarget.Length)
        //    {
        //        if (isPass(array))
        //        {
        //            copyList.Add(array.Clone());
        //        }
        //        return;
        //    }


        //    //生成长度为14的-1数组
        //    int[] arrLow = new int[15];
        //    for (int counst = 0; counst < arrLow.Length; counst++)
        //    {
        //        arrLow[counst] = -1;
        //    }

        //    for (int i=0;i<array.GetLength(0);i++)
        //    {
        //        for(int j=0;j<array.GetLength(1);j++)
        //        {
        //            if (i == 0&&j==0)
        //            {
        //                arrLow[0] = lowBegin;
        //                for(int counst=0;counst<arrTarget.Length; counst++)
        //                {
        //                    array[i, j] = arrTarget[lowBegin];
        //                }
        //            }
        //            addElement(array, arrTarget, arrLow, i, j);
        //        }
        //    }

        //    createNewD((int[,])array.Clone(), arrTarget, lowBegin + 1,copyList);
        //}

        //static void addElement(int[,] arry,int[] arrTarget, int[] arrLow, int line, int row)
        //{
        //    bool cantPass = true;
        //    for (int i = 0; i < arrTarget.Length; i++)
        //    {
        //        cantPass = false;
        //        int j = 0;
        //        for (; j < arrLow.Length&&arrLow[j]!=-1; j++)
        //        {
        //            if (i== arrLow[j])
        //            {
        //                cantPass = true;
        //            }

        //        }
        //        if (!cantPass)
        //        {
        //            arry[line, row] = arrTarget[i];
        //            arrLow[j] = i;
        //            break;
        //        }
        //    }
        //}

    }
}
